package UnionFindSet;


/*
    并查集
    这里的两个集合采用双向链表存储
 */
public class LinkedUnionFindSet {
    private Node nodes[];

    public LinkedUnionFindSet(int n) {
        nodes = new Node[n];
        for (int i = 0; i < n; i++) {
            nodes[i] = new Node();
        }
    }

    //union函数：把i，j所在的集合合并
    public void union(int i, int j) {
        boolean inSameSet = find(i, j);
        if (inSameSet) return;//说明i，j已经在同一个集合中了，不需要合并
        Node li = nodes[i].r;
        Node lj = nodes[i].r;
        Node liTail = nodes[i].prev;
        Node ljTail = nodes[i].prev;
        //把后一个链表链到前一个链表的尾部
        liTail.next = lj;
        lj.prev = liTail;
        ljTail.next = li;
        li.prev = ljTail;
        //接下来把j里面所有节点的r域指向前面链表节点r域所指向的位置
        Node p = lj;
        while (p != ljTail) {
            p.r = li.r;
        }
        ljTail.r = li.r;
    }

    private boolean find(int i, int j) {
        return nodes[i].r == nodes[j].r;
    }

}

class Node {
    public Node prev = this;
    public Node next = this;
    //r域指向头节点，表示自己属于哪个集合
    public Node r = this;
}